import collections


class Solution(object):
    def minNumberOfSemesters(self, n, relations, k):
        c = collections.defaultdict(set)
        for u, v in relations:
            c[v - 1].add(u - 1)
        already = set()
        already.add(0)
        st = {0}
        dist = 0
        while True:
            dist += 1
            next_st = set()
            for node in st:
                wait_list = []
                for i in range(n):
                    if (node >> i) & 1 == 0:
                        flag = True
                        for u in c[i]:
                            if (node >> u) & 1 == 0:
                                flag = False
                                break
                        if flag:
                            wait_list.append(i)
                if len(wait_list) <= k:
                    next_node = node
                    for index in wait_list:
                        next_node |= (1 << index)
                    if next_node == 2 ** n - 1:
                        return dist
                    if next_node not in already:
                        next_st.add(next_node)
                        already.add(next_node)
                else:
                    m = len(wait_list)
                    for val in range(1 << m):
                        if val.bit_count() == k:
                            next_node = node
                            for j in range(m):
                                if (val >> j) & 1:
                                    next_node |= (1 << wait_list[j])
                            if next_node not in already:
                                already.add(next_node)
                                next_st.add(next_node)
            st = next_st


data = Solution()
n = 4
relations = [[2, 1], [3, 1], [1, 4]]
k = 2
print(data.minNumberOfSemesters(n, relations, k))
n = 5
relations = [[2, 1], [3, 1], [4, 1], [1, 5]]
k = 2
print(data.minNumberOfSemesters(n, relations, k))
n = 11
relations = []
k = 2
print(data.minNumberOfSemesters(n, relations, k))